package leetcode.回溯DFS;

public class Leetcode1140 {
    public int stoneGameII(int[] piles) {
        int n = piles.length;
        int[] preSum = new int[n + 1];
        int[][] dp = new int[n][2*n];
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + piles[i];
        }
        return dfs(piles,0,1,preSum,dp);

    }


    public int dfs(int[] piles,int left,int M,int[] preSum,int[][] dp){
        if(left==piles.length){
            return 0;
        }
        if(dp[left][M]!=0){
            return dp[left][M];
        }
        if(piles.length-left<=2*M){
            return preSum[piles.length] - preSum[left];
        }
        int min = Integer.MAX_VALUE;
        for(int i = 1;i<=2*M;i++){
            min = Math.min(min,dfs(piles,left+i,Math.max(M,i),preSum,dp));
        }
        return dp[left][M]= preSum[piles.length] - preSum[left] -min;
    }
}
